package LeetCode.LC120;

import java.util.List;

/**
 * 120. 三角形最小路径和
 * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 * <p>
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 *
 * @author corn
 * @create 2020-10-29-9:40
 */
public class Solution {
    private Integer[][] numn;
    public int minimumTotal(List<List<Integer>> triangle) {
        numn = new Integer[triangle.size()][triangle.size()];
        return find(triangle, 0, 0);

    }

    /**
     * @param triangle
     * @param index
     * @param state
     * @return
     */
    public Integer find(List<List<Integer>> triangle, int index, int state) {
        //1、判断是否到达最底层
        if (state == triangle.size()) {
            return 0;
        }
        if(numn[state][index] != null){
            return numn[state][index];
        }
        return numn[state][index] = triangle.get(state).get(index) + Math.min(find(triangle, index, state + 1), find(triangle, index + 1, state + 1));
    }
}
